LeetCode 155. Min Stack

155. Min Stack（最小栈）

链接

https://leetcode-cn.com/problems/min-stack

题目

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

思路

这里用了两个栈，一个栈用于存放数据，一个栈用于存放最小值。
对于新的数据，如果x小于最小值栈的栈顶，那就将这个数字进入最小值栈，不然就将栈顶数字再入栈一次，出栈的时候两个一起出。

代码

 Stack<Integer> stackdata;
 Stack<Integer> stackmin;

/* public MinStack() {
   stackdata = new Stack<>();
   stackmin = new Stack<>();
 }*/

 public void push(int x) {
   stackdata.push(x);

   if (stackmin.empty()) {
     stackmin.push(x);
   } else if (x < stackmin.peek()) {
     stackmin.push(x);
   } else {
     stackmin.push(stackmin.peek());
   }
 }

 public void pop() {
   if (!stackdata.empty()) {
     stackdata.pop();
     stackmin.pop();
   }
 }

 public int top() {
   return stackdata.peek();
 }

 public int getMin() {
   return stackmin.peek();
 }